package com.thoughtworks.util;

import java.util.ArrayList;
import java.util.List;

import com.thoughtworks.exception.NoPathException;
import com.thoughtworks.model.Edge;

/**
 * @author Administrator
 *
 */
public class FindTripUtil {
	
	/**
	 * @param allEdges  : all edges of graph 
	 * @param startNode : start node of trip
	 * @param endNode   : end node of trip
	 * @return          : all nonredundant trips that meet the requirements
	 * @throws NoPathException
	 */
	public static List<List<Edge>> getNonredundantTrips(List<Edge> allEdges, 
			String startNode, String endNode) throws NoPathException {
		List<List<Edge>> trips = new ArrayList<List<Edge>>();
		findNonredundantPaths(trips, allEdges, new ArrayList<Edge>(), startNode, endNode);
		if(trips.size() == 0) {
			throw new NoPathException();
		}
		return trips;
	}
	
	
	/**
	 * @param allEdges  : all edges of graph
	 * @param max_stops : max stop count
	 * @param startNode : start node of trip
	 * @param endNode   : end node of trip
	 * @return          : all trips that meet the requirements, with the max total stop count
	 * @throws NoPathException
	 */
	public static List<List<Edge>> getTripsWithMaxStopCount(List<Edge> allEdges, int max_stops, 
			String startNode, String endNode) throws NoPathException {
		List<List<Edge>> trips = new ArrayList<List<Edge>>();
		findPathsWithMaxStopCount(trips, allEdges, new ArrayList<Edge>(), max_stops, startNode, endNode);
		if(0 == trips.size()) {
			throw new NoPathException();
		}
		return trips;
	}
	
	
	/**
	 * @param allEdges  : all edges of graph
	 * @param stopCount : stop count
	 * @param startNode : start node of trip
	 * @param endNode   : end node of trip
	 * @return          : all trips that meet the requirements, with the total stop count
	 * @throws NoPathException
	 */
	public static List<List<Edge>> getTripsWithStopCount(List<Edge> allEdges, int stopCount, 
			String startNode, String endNode) throws NoPathException {
		List<List<Edge>> trips = new ArrayList<List<Edge>>();
		findPathsWithStopCount(trips, allEdges, new ArrayList<Edge>(), stopCount, startNode, endNode);
		if(0 == trips.size()) {
			throw new NoPathException();
		}
		return trips;
	}
	
	
	/**
	 * @param allEdges     : all edges of graph
	 * @param max_distance : max distance of trip
	 * @param startNode    : start node of trip
	 * @param endNode      : end node of trip
	 * @return             : all trips that meet the requirements, with the max total distance of trip
	 * @throws NoPathException
	 */
	public static List<List<Edge>> getTripsWithMaxDistance(List<Edge> allEdges, int max_distance, 
			String startNode, String endNode) throws NoPathException {
		List<List<Edge>> trips = new ArrayList<List<Edge>>();
		findPathsWithMaxDistance(trips, allEdges, new ArrayList<Edge>(), max_distance, startNode, endNode);
		if(0 == trips.size()) {
			throw new NoPathException();
		}
		return trips;
	}
	
	
	/**
	 * @param allEdges  : all edges of graph
	 * @param distance  : distance of trip
	 * @param startNode : start node of trip
	 * @param endNode   : end node of trip
	 * @return          : all trips that meet the requirements, with the total distance of trip
	 * @throws NoPathException
	 */
	public static List<List<Edge>> getTripsWithDistance(List<Edge> allEdges, int distance, 
			String startNode, String endNode) throws NoPathException {
		List<List<Edge>> trips = new ArrayList<List<Edge>>();
		findPathsWithDistance(trips, allEdges, new ArrayList<Edge>(), distance, startNode, endNode);
		if(0 == trips.size()) {
			throw new NoPathException();
		}
		return trips;
	}
	
	
	/**
	 * @param allEdges : all edges of trip
	 * @param trip     : the fix trip, pattern like A-B-C
	 * @return         : all edges of the fix trip
	 * @throws NoPathException
	 */
	public static List<Edge> getFixTrip(List<Edge> allEdges, String trip) throws NoPathException {
		List<Edge> fix_edges = new ArrayList<Edge>();
		
		String raw_trip = trip.replace("-", "");
		
		for(int i=0; i<raw_trip.length()-1; i++) {
			String startNode = raw_trip.substring(i, i+1);
			String endNode = raw_trip.substring(i+1, i+2);
			for(Edge edge : allEdges) {
				if(edge.startWith(startNode) && edge.endWith(endNode)) {
					fix_edges.add(edge);
					break;
				}
			}
		}
		
		if(fix_edges.size() != raw_trip.length()-1) {
			throw new NoPathException();
		}
		return fix_edges;
		
	}
	
	/**
	 * @param trip : calculate of total distance of trip
	 * @return     : the total distance of the fix trip
	 */
	public static int calcDistanceOfTrip(List<Edge> trip) {
		int sum_distance = 0;
		for(Edge edge : trip) {
			sum_distance += edge.getWeight();
		}
		return sum_distance;
	}
	
	
	private static void findNonredundantPaths(List<List<Edge>> trips, List<Edge> allEdges, List<Edge> visitedEdges, 
			String startNode, String endNode) {
		for(Edge edge : allEdges) {
			if(visitedEdges.contains(edge)) {
				continue;
			}
			if(edge.startWith(startNode)) {
				visitedEdges.add(edge);
				if(edge.endWith(endNode)) {
					List<Edge> trip = new ArrayList<Edge>();
					trip.addAll(visitedEdges);
					trips.add(trip);
				}
				findNonredundantPaths(trips, allEdges, visitedEdges, edge.getEndNode(), endNode);
				visitedEdges.remove(edge);
			}
		}
	}
	
	private static void findPathsWithMaxStopCount(List<List<Edge>> trips, List<Edge> allEdges, List<Edge> visitedEdges,
			int max_stops, String startNode, String endNode) {
		for(Edge edge : allEdges) {
			if(edge.startWith(startNode)) {
				if(max_stops - 1 < 0) {
					continue;
				}
				max_stops--;
				visitedEdges.add(edge);
				if(edge.endWith(endNode)) {
					List<Edge> trip = new ArrayList<Edge>();
					trip.addAll(visitedEdges);
					trips.add(trip);
				}
				findPathsWithMaxStopCount(trips, allEdges, visitedEdges, max_stops, edge.getEndNode(), endNode);
				visitedEdges.remove(visitedEdges.size() - 1);
				max_stops++;
			}
		}
	}
	
	private static void findPathsWithStopCount(List<List<Edge>> trips, List<Edge> allEdges, List<Edge> visitedEdges,
			int stopCount, String startNode, String endNode) {
		for(Edge edge : allEdges) {
			if(edge.startWith(startNode)) {
				if(stopCount - 1 < 0) {
					continue;
				}
				stopCount--;
				visitedEdges.add(edge);
				if(edge.endWith(endNode) && 0 == stopCount) {
					List<Edge> trip = new ArrayList<Edge>();
					trip.addAll(visitedEdges);
					trips.add(trip);
				}
				findPathsWithStopCount(trips, allEdges, visitedEdges, stopCount, edge.getEndNode(), endNode);
				visitedEdges.remove(visitedEdges.size() - 1);
				stopCount++;
			}
		}
	}
	
	private static void findPathsWithMaxDistance(List<List<Edge>> trips, List<Edge> allEdges, List<Edge> visitedEdges,
			int max_distance, String startNode, String endNode) {
		for(Edge edge : allEdges) {
			if(edge.startWith(startNode)) {
				if(max_distance - edge.getWeight() < 0) {
					continue;
				}
				max_distance -= edge.getWeight();
				visitedEdges.add(edge);
				if(edge.endWith(endNode)) {
					List<Edge> trip = new ArrayList<Edge>();
					trip.addAll(visitedEdges);
					trips.add(trip);
				}
				findPathsWithMaxDistance(trips, allEdges, visitedEdges, max_distance, edge.getEndNode(), endNode);
				visitedEdges.remove(visitedEdges.size() - 1);
				max_distance += edge.getWeight();
			}
		}
	}	
	
	private static void findPathsWithDistance(List<List<Edge>> trips, List<Edge> allEdges, List<Edge> visitedEdges,
			int distance, String startNode, String endNode) {
		for(Edge edge : allEdges) {
			if(edge.startWith(startNode)) {
				if(distance - edge.getWeight() < 0) {
					continue;
				}
				distance -= edge.getWeight();
				visitedEdges.add(edge);
				if(edge.endWith(endNode) && 0 == distance) {
					List<Edge> trip = new ArrayList<Edge>();
					trip.addAll(visitedEdges);
					trips.add(trip);
				}
				findPathsWithDistance(trips, allEdges, visitedEdges, distance, edge.getEndNode(), endNode);
				visitedEdges.remove(visitedEdges.size() - 1);
				distance += edge.getWeight();
			}
		}
	}
}
